from LeetCoder import *


class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        sx, sy = start[0], start[1]
        tx, ty = target[0], target[1]
        n = len(specialRoads)
        dp = [inf] * n

        def min(a: int, b: int):
            return a if a < b else b

        def f(a, b, c, d):
            return abs(a-c) + abs(b - d)

        for _ in range(n):
            for i in range(n):
                x, y, o, p, c = specialRoads[i]
                dp[i] = min(dp[i], min(f(o, p, tx, ty) + c, f(x, y, tx, ty)))
                for j in range(n):
                    dp[i] = min(dp[i], min(dp[j] + c + f(o, p, specialRoads[j][0],
                                specialRoads[j][1]), dp[j] + f(x, y, specialRoads[j][0], specialRoads[j][1])))
        ans = abs(sx - tx) + abs(sy - ty)
        for i in range(n):
            x, y, o, p, c = specialRoads[i]
            ans = min(ans, f(sx, sy, x, y) + dp[i])
        return ans


s = Solution()
print(s.minimumCost([1, 1],
                    [8, 10],
                    [[4, 2, 1, 7, 1], [2, 10, 4, 10, 1], [7, 5, 7, 7, 4], [6, 6, 3, 2, 2], [8, 1, 4, 2, 4]]))  # == 14
print(s.minimumCost([1, 1],
                    [10, 8],
                    [[6, 4, 9, 7, 1], [5, 2, 2, 1, 3], [3, 2, 5, 5, 2]]) == 10)
print(s.minimumCost([1, 1],
      [5, 10],
      [[3, 4, 5, 2, 5], [4, 5, 3, 8, 3], [3, 2, 5, 3, 1]]) == 11)
print(s.minimumCost(start=[1, 1], target=[4, 5],
      specialRoads=[[1, 2, 3, 3, 2], [3, 4, 4, 5, 1]]) == 5)
print(s.minimumCost(start=[3, 2], target=[5, 7], specialRoads=[
      [3, 2, 3, 4, 4], [3, 3, 5, 5, 5], [3, 4, 5, 6, 6]]) == 7)
